#define  _CRT_SECURE_NO_WARNINGS
class Solution {
    typedef long long LL;
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) return 0;
        vector<vector<LL>> dp(n, vector<LL>(n));

        unordered_map<LL, list<LL>> hash;
        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);

        int ret = 0;
        for (int i = 2; i < n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                LL tgt = 2 * (LL)nums[j] - nums[i];
                if (hash.count(tgt))
                {
                    for (auto& e : hash[tgt])
                    {
                        if (e < j)
                            dp[j][i] += dp[e][j] + 1;
                        else
                            break;
                    }
                    ret += dp[j][i];
                }
            }
        }

        return ret;
    }
};